#include <stdio.h>
#include <stdlib.h>

#define MAX_V 6  // 顶点数（A-F）
#define MAX_E 10 // 边数

typedef struct
{
    int src, dest, weight;
} Edge;

typedef struct
{
    Edge edges[MAX_E];
    char vertexNames[MAX_V];
    int vCount, eCount;
} Graph;

// 创建图
Graph *createGraph()
{
    Graph *g = (Graph *)malloc(sizeof(Graph));
    g->vCount = 0;
    g->eCount = 0;
    return g;
}

// 添加顶点
void addVertex(Graph *g, char name)
{
    if (g->vCount >= MAX_V)
    {
        printf("Error: Graph is full\n");
        return;
    }
    g->vertexNames[g->vCount++] = name;
}

// 添加带权边
void addEdge(Graph *g, int src, int dest, int weight)
{
    if (g->eCount >= MAX_E)
    {
        printf("Error: Too many edges\n");
        return;
    }
    g->edges[g->eCount].src = src;
    g->edges[g->eCount].dest = dest;
    g->edges[g->eCount].weight = weight;
    g->eCount++;
}

// 查找父结点（用于检测环）
int find(int parent[], int i)
{
    while (parent[i] != i)
        i = parent[i];
    return i;
}

// 按权值排序的比较函数
int compare(const void *a, const void *b)
{
    Edge *e1 = (Edge *)a;
    Edge *e2 = (Edge *)b;
    return e1->weight - e2->weight;
}

// Kruskal算法实现
void kruskalMST(Graph *g)
{
    Edge result[MAX_V]; // 存储MST结果
    int parent[MAX_V];
    int resCount = 0;
    int totalWeight = 0;
    // 初始化父结点数组
    for (int v = 0; v < g->vCount; v++)
        parent[v] = v;
    // 按权值排序所有边
    qsort(g->edges, g->eCount, sizeof(g->edges[0]), compare);
    // 遍历排序后的边
    for (int i = 0; resCount < g->vCount - 1 && i < g->eCount; i++)
    {
        Edge nextEdge = g->edges[i];
        int x = find(parent, nextEdge.src);
        int y = find(parent, nextEdge.dest);
        // 如果不形成环，则加入结果集
        if (x != y)
        {
            result[resCount++] = nextEdge;
            parent[y] = x; // 合并集合
            totalWeight += nextEdge.weight;
        }
    }
    // 打印结果
    printf("Minimum Spanning Tree (Kruskal's Algorithm):\n");
    for (int i = 0; i < resCount; i++)
    {
        printf("%c - %c : %d\n",
               g->vertexNames[result[i].src],
               g->vertexNames[result[i].dest],
               result[i].weight);
    }
    printf("Total Weight: %d\n", totalWeight);
}

// 销毁图
void destroyGraph(Graph *g)
{
    free(g);
}

int main()
{
    // 创建图
    Graph *g = createGraph();

    // 添加顶点（A-F）
    addVertex(g, 'A');
    addVertex(g, 'B');
    addVertex(g, 'C');
    addVertex(g, 'D');
    addVertex(g, 'E');
    addVertex(g, 'F');

    // 添加带权边（按照题目要求）
    addEdge(g, 0, 1, 1); // A-B 1
    addEdge(g, 0, 2, 4); // A-C 4
    addEdge(g, 0, 3, 4); // A-D 4
    addEdge(g, 0, 4, 6); // A-E 6
    addEdge(g, 0, 5, 5); // A-F 5
    addEdge(g, 1, 2, 5); // B-C 5
    addEdge(g, 2, 3, 2); // C-D 2
    addEdge(g, 3, 4, 6); // D-E 6
    addEdge(g, 4, 5, 3); // E-F 3
    addEdge(g, 5, 1, 6); // F-B 6

    // 计算并打印最小生成树
    kruskalMST(g);

    // 销毁图
    destroyGraph(g);
    return 0;
}